/**
 *  LRU:最近最少使用缓存 满足两个要求：
 * 固定容量：最多存capacity个键值对
 * 如果容量满了，插入新值会淘汰最久没使用的旧值
 */

var LRUCache = class {
    constructor(capacity) {
        this.cache = new Map();
        this.capacity = capacity;
    }


    /**
     * 获取 key 对应的值
     * 如果存在，说明被使用了，需更新其顺序：先删除再添加到末尾
     * 如果不存在，返回 -1
     */
    get(key){
        let cache = this.cache;
        if(cache.has(key)){
            let temp = cache.get(key);
            cache.delete(key);
            cache.set(key, temp);
            return temp;
        } else {
            return -1;
        }
    }

    /**
     * 插入或更新 key 对应的值
     * 如果 key 已存在，先删除旧位置（以便更新顺序）
     * 如果 cache 已满，删除最久未使用的键（Map 的第一个键）
     * 然后将新 key 添加到 Map 尾部（表示最近使用）
     */
    put(key, value){
        let cache = this.cache;
        if(cache.has(key)){
            cache.delete(key);
        } else if(cache.size >= this.capacity) {
            cache.delete(cache.keys().next().value);
        }
        cache.set(key,value);
    }
}


